public class PossiblePath {

	public static void main(String[] args) {
		PossiblePath pp = new PossiblePath();
		System.out.println(pp.getPossiblePath(5, 4));
		System.out.println(pp.getPossiblePath2(5, 4));
	}

	public long getPossiblePath(int x, int y) {
		return factorial(x + y) / (factorial(x) * factorial(y));
	}

	public int getPossiblePath2(int x, int y) {
		int[][] pNum = new int[x + 1][y + 1];

		for (int i = 0; i < x + 1; ++i)
			pNum[i][0] = 1;
		for (int i = 0; i < y + 1; ++i)
			pNum[0][i] = 1;

		for (int i = 1; i < x + 1; ++i)
			for (int j = 1; j < y + 1; ++j)
				pNum[i][j] = pNum[i - 1][j] + pNum[i][j - 1];

		return pNum[x][y];
	}

	private long factorial(int n) {
		long f = 1;
		for (; n != 0; --n) {
			f *= (long) n;
		}
		return f;
	}
}
